/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-01-30
 * Time: 21:03
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
//     思路:
//     一: 先遍历一遍得到链表的长度, 再第二遍直接遍历到要删除的节点的前一个节点, 然后进行删除
//     二: 利用栈, 先遍历一遍 存入栈中, 再出来 n 个, 此时栈顶元素就是前一个元素
//     三: 双指针, 快指针先走, 至两个指针相差 n, 再同时移动, 至 快指针为空, 那么慢指针, 此时指向 要删除的节点的前一个
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null||head.next==null){
            return null;
        }
        ListNode prev=null; // 记录前驱节点
        ListNode left=head;
        ListNode right=head;
        // 右指针先走, 使两指针之间的距离固定
        while(n>0){
            right=right.next;
            n--;
        }
        // 走到右指针为空
        while(right!=null){
            right=right.next;
            prev=left; // 左指针走之前, 先记录前驱节点
            left=left.next;
        }
        // 前驱节点为空, 说明要删除的就是头节点
        if(prev==null){
            head=head.next;
        }else{
            prev.next=left.next;
        }
        return head;
    }
}
